# 二叉树展开为链表： https://leetcode-cn.com/problems/flatten-binary-tree-to-linked-list/solution/

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


# 最开始自己的想法，有错误，不知道出在哪里，改了几次（错误）    
class Solution:
    def flatten(self, root: TreeNode) -> None:
        """
            # 拆分最小子问题： 当只有三个结点的时候， 根节点和左右子节点
            # 1. 左右子节点都没有，直接返回节点
            if not node.left and not node.right:
                return node
            
            # 2. 左右子节点都有
            if node.left and node.right:
                temp = node.right
                node.right = node.left
                node.right.right = temp
                node.left = None
                return None
            # 3. 只有左节点
            elif node.left:
                node.right = node.left
                node.left = None
                return node
            # 4. 只有右节点
            elif node.right:
                return node

            
        """

        def dfs(node, right):
            # 终止条件, 叶子结点直接返回, 要注意，按照前序遍历的顺序， 左子树的最后节点，再接右子树
            if not node.left and not node.right:
                node.right = right
                return node

            if node.left and node.right:
                print(node.left.val, node.right.val)
                temp = dfs(node.right, None)
                node.right = dfs(node.left, temp)
                node.left = None
                return node

            if node.left is not None:
                node.right = dfs(node.left, None)
                node.left = None
                return node
            if node.right is not None:
                node.right = dfs(node.right, None)
                return node

        return dfs(root, None)            


# 正确写法，显示栈。 还请仔细分析代码，就多了一点内容，并结合例子，分析运行过程
class Solution:
    def flatten(self, root: TreeNode) -> None:
        """
            显示栈实现，边遍历边边串联 来分析下问题：
            1. 按照线性 先序顺序输出 2. 左指针为 None， 右指针指向下一元素

            之前的错误想法，还需要分析，左右子节点三种情况和 插入。
            现在换种思路：
            1. 单纯的求出来，前序遍历
            2. 前序遍历时的顺序，就是我们想要的顺序！ 我们只需要将前一个节点的left指针置为 None，右指针置为 当前节点即可！
            需要之一前序指针，pre， 指向当前节点的上一个节点
        """
        if not root: return []
        stack = list()           
        stack.append(root)
        pre = None
        while stack:
            node = stack.pop()
            # 1. 更新指针
            if pre:
                pre.left = None
                pre.right = node

            # 2. 添加左右子节点进去，正常的遍历逻辑
            if node.right: stack.append(node.right)
            if node.left: stack.append(node.left)
            
            # 3. 更新pre指针为当前节点
            pre = node

        return root


# 那么还可以写出它的递归版本， 有所不同，经过分析，不能使用前序遍历
class Solution:
    def flatten(self, root: TreeNode) -> None:
        """
            利用递归的方式，前序遍历不是很好写。 因为 根 左 右的方式。 拼接。 
            加入根节点为 node ， 那么 1. node.right = node.left   2. 此时，node.right 被 node.left代替掉了！ 无法进行后续操作了

            # 解决： 采用 后序：  右， 根， 左的方式
            1. 将右节点，连在左节点上， 2. 再将左节点连到根节点的 右指针上 避免了冲突
        """
        if not root: return []
        pre = None
        def dfs(node):
            nonlocal pre
            if not node: return 
            
            # 右， 左， 根的遍历
            dfs(node.right)
            dfs(node.left)
            # 根处理时，左指针设置为 None， 右指针要指向前一个遍历的节点
            if pre:
                node.right = pre
                node.left = None
                
            pre = node

        dfs(root)
        return root


# 通过上面两个实现，理解本质后，还可以使用非递归的实现，O(1) 空间复杂度！！
class Solution:
    def flatten(self, root: TreeNode) -> None:
        """
            通过上面两个方法的实现，可以发现：
            1. 一个节点的右子树，一定是挂在它的左子树的最右节点的右指针上
            2. 节点的左子树再挂到 节点的右指针上
            3. 节点左指针 置为 None

            这个过程当前的节点处理完毕， 节点移动到它的右节点， 继续重复这个过程，直到所有的节点都经过这一过程，变得正确！
        """
        cur = root
        while cur:
            if cur.left:
                # 1. 找左子树最右节点
                temp = cur.left
                while temp.right:
                    temp = temp.right
                # 2. 链接右子树
                temp.right = cur.right
                # 3. 左子树移到右子树，并左指针置为 None
                cur.right = cur.left
                cur.left = None
                # cur 后移
                cur = cur.right
            else:
                cur = cur.right
            # 当然可以优化 if else 语句，这里使逻辑更清晰
        return root